1. Field of the Invention
The invention relates in general to a system for determining positions for modules within an analog integrated circuit (IC) and in particular for a system for positioning modules within an IC containing symmetric circuits.
2. Description of Related Art
A netlist describes an analog IC as including a set of interconnected device modules such as transistors, capacitors, resistors and other devices. A computer-based placement tool processes a netlist to determine a suitable position and orientation within the IC for each device module. To reduce the effect of parasitic mismatches and circuit sensitivity to thermal gradients or process variations, a placement tool will try to place pairs of matching modules close to one another and symmetrically with respect to one another with respect to a common axis. The circuit designer will normally provide the placement tool with a set of symmetry constraints identifying each group of modules (a “symmetry group”) that is to have a symmetric layout, identifying each pair of matching devices (a “symmetry pair”) within each symmetry group that is to be placed symmetrically about an axis of the symmetry group, and identifying each internally symmetric module (a “self-symmetry module”) within the group that is to be centered on the symmetry group axis.
When generating a placement plan, a placement tool typically treats each module of an IC as a rectangle that is large enough to accommodate the device module and to provide some additional space around the device module for routing the conductors (“nets”) that are to interconnect device modules. The problem of selecting a position for each module of the IC becomes one of finding a non-overlapping position within a plane for each of a set of rectangles of various sizes and shapes in a way that satisfies various symmetry and other constraints on device module placement.
FIG. 1A shows a placement for a symmetry group that is symmetric about a vertical axis 10 and FIG. 1B shows a placement for a symmetry group that is symmetric about a horizontal axis 12. The following notation is used in FIGS. 1A and 1B and elsewhere in this specification.
Sa symmetry groupbia module(bi, bi′)a symmetry pairbisa self-symmetry moduleThe following expression can represent the symmetry group S of FIG. 1A:S=((b1, b1′), (b2, b2′), b3s)
A placement plan for an analog IC must satisfy other constraints in addition to symmetry constraints including, for example, constraints on available space and constraints on positions and orientations of certain modules. Although many different IC placements may satisfy all constraints, designers consider some placements to be better than others based on a number of factors. For example, designers usually consider a placement that positions highly interconnected modules near one another to be better because it reduces the lengths of the net needed to interconnect module terminals, thereby making it more likely that a computer-based routing tool will be able to route the nets between modules positioned in accordance with the placement plan. A more compact placement may be considered better when it can result in a smaller or faster IC. Placement tools commonly generate several different trial placements and evaluate each trial placement based on a “cost function” having a value that is a weighted sum of various attributes of the trial placement such as variables representing estimated lengths of the nets (“wire lengths”), the total placement area and other factors. The trial placement having the lowest cost function value is selected as the most suitable placement.
One way to generate a large number of trial placements is to start with an initial placement and then iteratively perturb the initial placement by changing positions and orientations of the device modules to produce many trial placements, and to evaluate a cost function for each trial placement to find a best placement. Much prior work in this area has been directed toward developing approaches for reducing the amount of processing time needed to arrive at a low cost placement solution while satisfying the symmetry constraints.
One way to reduce processing time is to represent a trial placement in a way that allows a placement tool to quickly and easily perturb a trial placement to produce a different placement. While it is possible for a placement tool to employ a topological representation of a trial placement that directly tracks the coordinates of each rectangle within an IC layout, it is difficult and time-consuming for a placement tool to iteratively perturb such a topological representation of a trial placement in order to create other trial placements because a change to coordinates of any one rectangle can have a ripple effect on coordinates of every other rectangle. The article, “B*-Trees: A New Representation For Non-slicing Floorplans,” Proc. DAC, pp. 458-463, 2000, describes a placement method employing a binary tree (“B*-tree”) to represent a compacted placement in which no module can move any further down or to the left. A B*-tree is a convenient way for a placement tool to represent a placement because it is relatively easy for the tool to alter a placement by altering the B*tree representation. FIG. 2A shows a compacted placement of a set of 10 modules b0-b9 and FIG. 2B shows a corresponding B*-tree representation of that placement wherein every node ni of the B*-tree corresponds to a module bi of the compacted placement. The root n0 of the B*-tree of FIG. 2B corresponds to the module b0 on the bottom-left corner of the placement of FIG. 2A. For each node ni corresponding to a module bi, the left child of node ni represents the lowest, adjacent module on the right side of module big while the right child of node ni represents the first module above bi having the same horizontal coordinate. The width and height dimensions (wi, hi) of the rectangular device module bi associated with each node god can be stored in a database.
Given a B*-tree representation of a compacted placement, a placement tool can, when necessary, calculate the coordinate (xi, yi) of each module through an ordered tree traversal. Suppose the module bi, represented by the node ni, has the bottom-left coordinate (xi, yi), width wi, and height hi. Then for the left child, nj, of ni, xj=xi+wi; for the right child, nk, of ni, xk=xi. A placement tool in accordance with the invention maintains a contour structure to calculate y-coordinates. Thus, starting from the root node, whose bottom-left coordinate is (0, 0), then visiting the root's left subtree, and then its right subtree, the tool can use a pre-order tree traversal procedure (B*-tree packing) to calculate all coordinates of the modules in the placement.
A B*-tree is a convenient way for a placement tool to represent a compacted trial placement that allows it to quickly perturb a trial placement by modifying its B*-tree representation and to quickly determine whether the placement satisfies some kinds of constraints by processing its B*-tree representation. For example it is possible to determine from a B*-tree representation whether a set of modules forming a symmetry group will satisfy symmetry constraints on the symmetry group. Once a placement tool has generated a B*-tree representation of a new trial placement and has processed the B*-tree representation to determine whether the trial placement it specifies will satisfy various symmetry and other constraints, the placement tool can quickly convert the B*-tree representation of the trial placement into physical locations that will enable it to conveniently determine whether the trial placement satisfies other constraints and to evaluate the cost function for that particular trial placement. However, a placement tool employing B*-tree placement representations can still require substantial amounts of processing time to find an optimal placement particularly for large analog ICs that include several symmetry groups because the solution space that must be searched can still be quite large.
U.S. Pat. No. 6,550,046, issued Apr. 15, 2003 to Balasa et al describes an automated method for packing cells in an analog IC layout including symmetry groups that are subject to symmetry constraints. Symmetry constraints are defined for each symmetry group, which are represented by sequence-pairs. To reduce the solution space, the initial sequence pair encoding is required to be symmetry-feasible so that the search subspace is therefore limited to symmetry-feasible sequence-pairs. Nevertheless, the solution space is also quite large because the sequence-pair representation does not preclude the devices in symmetry groups from being placed far apart, which will not be considered a good placement.
What is needed is an approach to analog IC placement that limits the search space to trial placements wherein device modules forming each symmetry group reside near one another and wherein each symmetry group satisfies all symmetry constraints.